package ups.MapParse;

public class DistanceCalculator {
	private int minimum( int a, int b, int c) {
		int min = a;
		if( b < min) {
			min = b;
		}
		
		if( c < min ) {
			min = c;
		}
		
		return min;
	}
	
	protected void prettyPrintTable( int[][] table, int m, int n ) {
		int i, j;
		for( i = 0; i <= m; i++ ) {
			for( j = 0; j <= n; j++ ) {
				System.out.print(table[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	public int distance2( String s, String t) {
	//	System.out.println( minimum( 1, 2, 3 ));
		int m = s.length();
		int n = t.length();
		
		int i, j; // iterators
		
		char s_i; // ith char of s
		char t_j; // jth char of t
		
		int[][] table = new int[m+1][n+1];
		int cost;
		
		if( n == 0 ) return m;
		if( m == 0 ) return n;
		
		for( i = 0 ; i <= m; i++ ) {
			table[i][0] = i;
		}
		
		for( j = 0; j <= n; j++ ) {
			table[0][j] = j;
		}
		
		for( i = 1; i <= m; i++ ) {
			//System.out.println("i = " + i); 
			s_i = s.charAt(i-1);
			for( j = 1; j <= n; j++ ) {
				t_j = t.charAt(j-1);
				
				if( s_i == t_j) {
					cost = 0;
				} else {
					cost = 1;
				}
				
				table[i][j] = minimum( table[i-1][j] + 1,
									   table[i][j-1] + 1,
									   table[i-1][j-1] + cost);
			}
			//System.out.println();
			//prettyPrintTable(table, m, n );
		}
	
		return table[m][n];
	}
	
	public int distance( String a, String b) {
		System.out.println("String a = " + a + " (" + a.length() + ")");
		System.out.println("String b = " + b + " (" + b.length() + ")");
		int[][] table = new int[a.length()+1][b.length()+1];
		
		int i, j;
		for( i = 0; i <= a.length(); i++ ) {
			table[i][0] = i;
		}
		
		for( j = 1; j <= b.length(); j++ ) {
			table[0][j] = j;
		}

		for( i = 0 ; i <= a.length(); i++ ) {
			for(j = 0 ; j <= b.length(); j++ ) {
				System.out.print( table[i][j] + " " );
			}
			System.out.println();
		}
		
		for( i = 1; i < a.length(); i++ ) {
			char ca = a.charAt(i);
			
			for( j = 1; j < b.length(); j++ ) {
				char cb = b.charAt(j);
				int cost;
				System.out.println( i + " , " + j);
				
				if( ca == cb ) {
					cost = 0;
				} else {
					cost = 1;
				}
				
				table[i][j] = minimum( table[i-1][j] + 1 , table[i][j-1] + 1, table[i-1][j-1] + cost );
				
			}
		}
		
		for( i = 0 ; i <= a.length(); i++ ) {
			for(j = 0 ; j <= b.length(); j++ ) {
				System.out.print( table[i][j] + " " );
			}
			System.out.println();
		}
		
		return table[a.length()][b.length()];
	}
}
